home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1998 August: Tool Chest / Dev.CD Aug 98 TC.toast / Sample Code / Processes / MP Threaded Sort / Sort / QuickSort.cp < prev    next >
Encoding:
Text File  |  1997-03-13  |  3.5 KB  |  156 lines  |  [TEXT/CWIE]
  1. /*----------------------------------------------------------------------------
  2.  
  3.     QuickSort.cp
  4.  
  5.     fastQSort() is a replacement for qsort().  Compared with the Think C library
  6.     version of qsort, fastQSort is about 3 times faster (it takes 1/3 the time), 
  7.     and its speed isn't dependent on the data being sorted.
  8.     
  9.     One problem with qsort is that when the data is not in random order -- for
  10.     example when it's already ordered, in reverse order, or almost sorted -- then 
  11.     qsort exhibits worst case behavior of N*N/2 operations.  For N=1024 this can 
  12.     take about 30 seconds, instead of the usual 0.8 seconds.  The fastQSort 
  13.     algorithm doesn't have this problem, because it randomly selects the pivot
  14.     element, and so for N=1024 it requires about 0.26 secs +/- 0.02 secs.
  15.     
  16.     Also, because fastQSort doesn't exhibit worst case behavior, it doesn't 
  17.     require as much stack space, even though it has 12 bytes more of local
  18.     variables.
  19.     
  20.     The things that make fastQSort so much faster than qsort are:
  21.     
  22.     1)    fastQSort picks the pivot element randomly, so it doesn't display worst
  23.         case behavior.
  24.         
  25.     2)    fastQSort uses pointers and pointer arithmetic, avoiding multiplication
  26.         whenever possible.
  27.     
  28.     3)    qsort uses std_swap() to swap the data between two locations, and 
  29.         std_swap loops through the data 3 times to perform the exchange!  In
  30.         comparison, swapMem() loops through the data just once.
  31.         
  32.     4)    fastQSort uses register variables whenever it makes good sense to do so.
  33.     
  34.     
  35.     Researched and written by:
  36.     
  37.         Haydn Huntley
  38.         Haydn's Consulting
  39.         203 West Stone
  40.         Fairfield, Iowa  52556
  41.         (515) 472-7025
  42.         
  43.     During the school year, I may be reached at the following address:
  44.     
  45.         Haydn Huntley
  46.         Eigenmann Hall #289
  47.         Indiana University
  48.         Bloomington, IN  47406
  49.         (812) 857-8620
  50.         
  51.     E-mail:  huntley@copper.ucs.indiana.edu
  52.  
  53.     This version was modified by Randy Thelen of Apple Computer, Inc.
  54.     This version works within the shell of SortPicts.
  55.     
  56.     Hopefully, we'll see faster Sorts with QuickSort than with Heap sorts and the like
  57. ----------------------------------------------------------------------------*/
  58.  
  59. #include "SortPicts.h"
  60.  
  61. void    QSort( SortPicts *sortPicts)
  62. {
  63.     sortPicts->QSort();
  64. }
  65.  
  66.  
  67. void    SortPicts::QSort( void)
  68. {
  69.         QuickSortEngine( 0, N);
  70. }
  71.  
  72.  
  73. void    SortPicts::ChooseMedian( long a, long b, long c)
  74. {
  75.     long        m;        //    median
  76.  
  77.     if( sortData[a] > sortData[b])
  78.         if( sortData[a] > sortData[c])
  79.             if( sortData[b] > sortData[c])
  80.                 m = b;
  81.             else
  82.                 m = c;
  83.         else
  84.             m = a;
  85.     else
  86.         if( sortData[a] > sortData[c])
  87.             m = a;
  88.         else
  89.             if( sortData[b] > sortData[c])
  90.                 m = c;
  91.             else
  92.                 m = b;
  93.     
  94.     if( a != m)
  95.         ExchangeSortItem( a, m);
  96. }
  97.  
  98.  
  99. void    SortPicts::QuickSortEngine( long left, long right)
  100. {
  101.     long            n;
  102.     long            i, j;
  103.     
  104.     while( (n = right - left) > 1)
  105.     {
  106.         if( n < kPivotCutoff)        //    Use a random pivot
  107.             ExchangeSortItem( left + Random( n), left);
  108.         else
  109.             ChooseMedian( left, left + (n >> 1), 
  110.                           left + Random( n));
  111.         
  112.         i = left;
  113.         j = right;
  114.         
  115.         while( 1)
  116.         {
  117.             i++;
  118.             while( (i < right) && (sortData[i] < sortData[left]))
  119.                 i++;
  120.             
  121.             j--;
  122.             while( (j > left) && (sortData[j] > sortData[left]))
  123.                 j--;
  124.             
  125.             if( i >= j)
  126.                 break;
  127.             
  128.             ExchangeSortItem( i, j);
  129.         }
  130.         
  131.         if( j == left)
  132.         {
  133.             left++;
  134.             continue;
  135.         }
  136.         
  137.         ExchangeSortItem( left, j);
  138.         if( (j - left) < (right - (j + 1)))
  139.         {
  140.             /* equivalent to doFastQSort (j + qSize, last);        */
  141.             /* to save stack space                                */
  142.             QuickSortEngine( left, j);
  143.             left = j + 1;
  144.         }
  145.         else
  146.         {
  147.             /* equivalent to doFastQSort (first, j);            */
  148.             /* to save stack space                                */
  149.             QuickSortEngine( j+1, right);
  150.             right = j;
  151.         }
  152.         
  153.     }
  154. }
  155.  
  156.